#include <stdio.h>

void insert_sort(int*, int);
void print_array(int*, int);

int main() {
    int a[6] = {5, 2, 4, 6, 1, 3};
    int n = sizeof(a)/sizeof(int);

    print_array(a, n);

    insert_sort(a, n);

    print_array(a, n);

    return 0;
}

/**
 * insert_sort
 * --------------------
 * 思路：
 * --------------------
 */
void insert_sort(int* a, int n){
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j > -1 && a[j] > key) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}

void print_array(int* a, int n){
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

